package com.atguigu.sort;

import com.atguigu.utils.ArrayGenerator;
import com.atguigu.utils.SortingHelper;
import org.junit.Test;

import java.util.Arrays;

public class InsertSortTest {

    public static void main(String[] args) {
        int[]dataSize={10000,100000};
        for(int n:dataSize){
            Integer[] arr1 = ArrayGenerator.generateRandomArray(n, n);
            Integer[] arr2=Arrays.copyOf(arr1,arr1.length);
            Integer[] arr3=Arrays.copyOf(arr1,arr1.length);
            SortingHelper.sortTest("InsertionSort",arr1);
            SortingHelper.sortTest("InsertionSort2",arr2);
            SortingHelper.sortTest("QuickSort",arr3);
        }
    }
    @Test
    public void test1(){
        Integer[]arr={89,54,34,19,89,18,34};
        InsertSort.Sort(arr);
        System.out.println(Arrays.toString(arr));
    }
    @Test
    public void test2(){
        int[]arr={89,54,34,19,89,18,34};
        InsertSort2(arr);
        System.out.println(Arrays.toString(arr));
    }
    public void InsertSort2(int[]arr){
        for(int i=0;i<arr.length;i++){
            int value=arr[i];
            for(int j=i;j>=0;j--){
                if(j==0||arr[j-1]<value){
                    arr[j]=value;
                    break;
                }else{
                    arr[j]=arr[j-1];
                }
            }
        }
    }
    @Test
    public void test3(){
        //换个方式实现插入排序法：arr[0,i)未排序；arr[i..n)已排序。
        int[]arr={89,54,34,19,89,18,34};
        InsertSort3(arr);
        System.out.println(Arrays.toString(arr));
    }
    public void InsertSort3(int[]arr){
        for(int i=arr.length-1;i>=0;i--){
            int value=arr[i];
            int j;
            for(j=i;j+1<arr.length&&arr[j+1]<value;j++){
                arr[j]=arr[j+1];
            }
            arr[j]=value;
        }
    }
    public static <E extends Comparable<E>>void Sort(E[]arr){
        for(int i=arr.length-1;i>=0;i--){
            E value=arr[i];
            int j;
            for(j=i;j+1<arr.length&&arr[j+1].compareTo(value)<0;j++){
                arr[j]=arr[j+1];
            }
            arr[j]=value;
        }
    }

}
